02. Examples of Path Planning

Terminology

Complete - An algorithm is complete if it is able to find a path between the start and the goal when one exists.

Optimal - An algorithm is optimal if it is able to find the best solution.

Bug Algorithm Quiz

In the video above you were introduced to the bug algorithm. The idea behind the algorithm is presented below:

Head directly towards the goal,

If an obstacle is encountered:

\quadTraverse the obstacle clockwise until you can follow the original path towards the goal again,

Repeat until arrived at goal.

The problem below will demonstrate one instance where a solution exists, but the bug algorithm is unable to find it.

In the above example, the robot would end up traversing the outer wall of the obstacle endlessly. There exist variants to the bug algorithm that will remedy this error, but the bulk of path planning algorithms rely on other principles that you will be introduced to throughout this lesson. In studying new algorithms, we will revisit the notion of Completeness and Optimality in analyzing the applicability of an algorithm to a task.